#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution
{
public:
    int minMoves(vector<string> &matrix)
    {
        const vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int row = matrix.size(), column = matrix[0].size();
        // index: x,y -> x,y  index = y*column+x;
        vector<vector<int>> gates(26,vector<int>(0));
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < column; j++)
            {
                if (matrix[i][j] != '.' && matrix[i][j] != '#')
                {
                    int index = i * column + j;
                    gates[matrix[i][j] - 'A'].push_back(index);
                }
            }
        }
        queue<int> openList;
        vector<vector<bool>> visited(matrix.size(), vector<bool>(matrix[0].size(), false));
        int step = 0;
        auto advancePush = [&](int index)
        {
            int x = index % column, y = index / column;
            openList.push(index);
            visited[y][x] = true;
            if (matrix[y][x] != '.' && matrix[y][x] != '#')
            {
                char c = matrix[y][x];
                for (int i : gates[c - 'A'])
                {
                    if (!visited[i / column][i % column])
                    {
                        openList.push(i);
                        visited[i / column][i % column] = true;
                    }
                }
            }
        };
        advancePush(0);
        bool success = false;
        while (!openList.empty() && !success)
        {
            step++;
            int size = openList.size();
            for (int i = 0; i < size; i++)
            {
                int index = openList.front();
                openList.pop();
                if (index == column * row - 1)
                {
                    success = true;
                    break;
                }
                int x = index % column, y = index / column;
                char c = matrix[y][x];
                for (auto &dir : dirs)
                {
                    int newX = x + dir[0], newY = y + dir[1];
                    if (newX >= 0 && newX < column && newY >= 0 && newY < row && !visited[newY][newX])
                    {
                        if (visited[newY][newX])
                            continue;
                        if (matrix[newY][newX] != '#')
                        {
                            visited[newY][newX] = true;
                            advancePush(newY * column + newX);
                        }
                    }
                }
            }
        }
        return success ? step - 1 : -1;
    }
};
int main()
{
    cout << "Code3552" << endl;
    Solution s;
    vector<string> m = {"A..", ".A.", "..."};
    // vector<string> m = {".#...", ".#.#.", ".#.#.", "...#."};
    // vector<string> m = {".", "#"};
    // vector<string> m = {".", "A"};
    cout << s.minMoves(m) << endl;
    return 0;
}